//https://leetcode.cn/problems/n-queens/
class Solution {
    List<List<String>> ret;
    char[][] path;
    boolean[] colCheck;
    boolean[] dig1Check;// 判断主对角线
    boolean[] dig2Check;// 判断副对角线
    int n;

    public List<List<String>> solveNQueens(int n_) {
        n = n_;
        ret = new ArrayList<>();
        path = new char[n][n];
        for(int i = 0; i < n; i++) 
            for(int j = 0; j < n; j++) path[i][j] = '.';
        colCheck = new boolean[n];
        dig1Check = new boolean[n * 2];
        dig2Check = new boolean[n * 2];
        dfs(0);
        return ret;
    }
    public void dfs(int row) {
        if(row == n) {
            //函数出口 & 完整的皇后棋盘的放法
            List<String> tmp = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                tmp.add(String.valueOf(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }
        for(int col = 0; col < n; col++) {
            if(colCheck[col] == false && dig1Check[row - col + n] == false && dig2Check[row + col] == false) {
                path[row][col] = 'Q';
                colCheck[col] = dig1Check[row - col + n] = dig2Check[row + col] = true;
                dfs(row + 1);
                //回溯
                path[row][col] = '.';
                colCheck[col] = dig1Check[row - col + n] = dig2Check[row + col] = false;
            }
        }
    }
}